Brace expansion

Time: O(PxLxLog(PL)); Space: O(PxL); medium*

A string S represents a list of words.

Each letter in the word has 1 or more options.

If there is one option, the letter is represented as is.

If there is more than one option, then curly braces delimit the options.

For example, “{a,b,c}” represents options [“a”, “b”, “c”].

For example, “{a,b,c}d{e,f}” represents the list [“ade”, “adf”, “bde”, “bdf”, “cde”, “cdf”].

Return all words that can be formed in this manner, in lexicographical order.

Example 1:

Input: S = “{a,b}c{d,e}f”

Output: [“acdf”,“acef”,“bcdf”,“bcef”]

Example 2:

Input: S = “abcd”

Output: [“abcd”]

Constraints:

• 1 <= len(S) <= 50

• There are no nested curly brackets.

• All characters inside a pair of consecutive opening and ending curly brackets are different.

1. Backtracking

Note that the string requires reformatting to divide chars can be backtracking.

import itertools

class Solution1(object):
    """
    Time: O(P*L*Log(P*L)), P is the production of all number of options , L is the length of a word
    Space: O(P*L)
    """
    def expand(self, S):  # nested is fine
        """
        :type S: str
        :rtype: List[str]
        """
        def form_words(options):
            words = list(map(''.join, itertools.product(*options)))
            words.sort()
            return words

        def generate_option(expr, i):
            option_set = set()
            while i[0] != len(expr) and expr[i[0]] != "}":
                i[0] += 1  # { or ,
                for option in generate_words(expr, i):
                    option_set.add(option)
            i[0] += 1  # }
            option = list(option_set)
            option.sort()
            return option

        def generate_words(expr, i):
            options = []
            while i[0] != len(expr) and expr[i[0]] not in ",}":
                tmp = []
                if expr[i[0]] not in "{,}":
                    tmp.append(expr[i[0]])
                    i[0] += 1  # a-z
                elif expr[i[0]] == "{":
                    tmp = generate_option(expr, i)
                options.append(tmp)
            return form_words(options)

        return generate_words(S, [0])

sol = Solution1()
S = "{a,b}c{d,e}f"
assert sol.expand(S) == ["acdf","acef","bcdf","bcef"]
S = "abcd"
assert sol.expand(S) == ["abcd"]

class Solution2(object):
    def expand(self, S):  # nested is fine
        """
        :type S: str
        :rtype: List[str]
        """
        def form_words(options):
            words = []
            total = 1
            for opt in options:
                total *= len(opt)
            for i in range(total):
                tmp = []
                for opt in reversed(options):
                    i, c = divmod(i, len(opt))
                    tmp.append(opt[c])
                tmp.reverse()
                words.append(''.join(tmp))
            words.sort()
            return words

        def generate_option(expr, i):
            option_set = set()
            while i[0] != len(expr) and expr[i[0]] != "}":
                i[0] += 1  # { or ,
                for option in generate_words(expr, i):
                    option_set.add(option)
            i[0] += 1  # }
            option = list(option_set)
            option.sort()
            return option

        def generate_words(expr, i):
            options = []
            while i[0] != len(expr) and expr[i[0]] not in ",}":
                tmp = []
                if expr[i[0]] not in "{,}":
                    tmp.append(expr[i[0]])
                    i[0] += 1  # a-z
                elif expr[i[0]] == "{":
                    tmp = generate_option(expr, i)
                options.append(tmp)
            return form_words(options)

        return generate_words(S, [0])

sol = Solution2()
S = "{a,b}c{d,e}f"
assert sol.expand(S) == ["acdf","acef","bcdf","bcef"]
S = "abcd"
assert sol.expand(S) == ["abcd"]

See also:

https://leetcode.com/problems/brace-expansion